import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

public class test {


    //二分查找

    public static  int binarySearch(int[] arr,int key){
        int left=0;
        int right=arr.length-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(arr[mid]>key){
                right=mid-1;
            }else if(arr[mid]<key){
                left=mid+1;
            }else{
                return mid;
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        int[] arr={71,23,31,14,75};
        System.out.println("排序前的数组"+Arrays.toString(arr));
        Arrays.sort(arr);//默认从小到大
        System.out.println("排序后的数组"+Arrays.toString(arr));
        int ret=Arrays.binarySearch(arr,31);  //数组自带的二分查找
        System.out.println(ret);
//        int ret=binarySearch(arr,9);
//        System.out.println(ret);
    }

    //查找效率比较低，因为需要挨个查找
    public static int findNum(int[] arr,int key){
        for (int i = 0; i < arr.length; i++) {
            if(arr[i]==key){
                return i;
            }
        }
        return -1;
    }

    public static void main47(String[] args) {
        int[] arr={1,2,3,4,5};
        int index=findNum(arr,9);
        System.out.println(index);
    }

    public static double sumAve(int[] arr){
        double sum=0;
        for (int i = 0; i < arr.length; i++) {
            sum+=arr[i];
        }
        sum/=arr.length;

        return sum;
    }
    public static void main46(String[] args) {
        int[] arr={1,2,3,4,5};
        double ave=sumAve(arr);
        System.out.println(ave);
    }


    public static String myToString(int[] array){
        String arr="[";
        for (int i = 0; i < array.length; i++) {
            arr+=array[i];
            if(i!=array.length-1){
                arr+=",";
            }
        }
        arr+="]";

        return arr;
    }
    public static void main45(String[] args) {
        int[] array={1,2,3,4,5};
        System.out.println(myToString(array));
    }

    //一个引用不可能同时指向多个对象

    //该引用不会修改实参的值，因为是新开辟了一块空间
    public static void funcc2(int[] arr){
        arr=new int[]{9,8,7,6,5};
    }

    //该引用可以修改实参的值
    public static void funcc1(int[] arr){
        arr[0]=99;
    }
    public static void main44(String[] args) {
        int[] arr={1,2,3,4,5};
        funcc1(arr);
        System.out.println(Arrays.toString(arr));
    }




    public static int[] func3(int[] arr1){
        int[] ret=new int[arr1.length];
        for (int i = 0; i < arr1.length; i++) {
            ret[i]=arr1[i]*2;
        }
        return ret;
    }
    public static void main43(String[] args) {

        int[] arr1={1,2,3,4,5};
        int[] temp=func3(arr1);
        System.out.println(Arrays.toString(arr1));
        System.out.println(Arrays.toString(temp));
    }
    //在数组自身进行修改
    public static int[] func2(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            arr[i]=arr[i]*2;
        }
        return arr;
    }
    //引用之间的赋值（重新申请一个数组）
    public static int[] func1(int[] arr){
        int[] ret=new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            ret[i]=arr[i]*2;
        }
        return ret;
    }

    public static void main42(String[] args) {
        int[] arr={1,2,3,4,5};
        System.out.println(Arrays.toString(arr));
        int[] temp=func2(arr);
        System.out.println(Arrays.toString(arr));
//        System.out.println(Arrays.toString(temp));
    }


    //array1这个引用，指向array2这个引用所指向的对象
    //当2个引用同时指向一个对象的时候，通过任何一个引用，都能修改这个对象的值

    //如果将来代码报错"空指针异常"，那么我们要做的是，
    //  找到这行代码中的引用。判断这个引用为什么是空的
    public static void main41(String[] args) {
        int[]  array1=new int[3];
        array1[0]=1;
        array1[1]=2;
        array1[2]=3;

        int[] array2=new int[]{1,2,3,4,5};
        array2[0]=100;
        array2[1]=200;
        array1=array2;
        array1[2]=300;
        array1[3]=400;
        array1[4]=500;
        for (int i = 0; i < array1.length; i++) {
            System.out.println(array1[i]);
        }
    }

    public static void main40(String[] args) {
        int[] array={1,2,3,4,5};
        System.out.println(array[2]);
        System.out.println(array);
        String str="abc";
        System.out.println(str);
    }

    public static  void move(char pos1,char pos2){
        System.out.print(" "+pos1+"->"+pos2+" ");
    }
    public static void Hanoi(int n,char pos1,char pos2,char pos3){
        if(n==1){
            move(pos1,pos3);
        }else{
            Hanoi(n-1,pos1,pos3,pos2);
            move(pos1,pos3);
            Hanoi(n-1,pos2,pos1,pos3);
        }
    }

    public static void main39(String[] args) {

         Hanoi(1,'A','B','C');
         System.out.println();
         Hanoi(2,'A','B','C');
         System.out.println();
        Hanoi(3,'A','B','C');
    }

    public static int sum1(int x,int y){
        return x+y;
    }

    public static double sum1(double x,double y,double z){
        return x+y+z;
    }

    public static void main38(String[] args) {
        int num1=10;
        int num2=12;
        double d1=12.5;
        double d2=17.5;
        double d3=15.5;

        int ret1=sum1(num1,num2);
        double ret2=sum1(d1,d2,d3);
        System.out.println(ret1);
        System.out.println(ret2);
    }

    public static int maxNum2(int x,int y){
        return x>y?x:y;
    }

    public static int maxNum3(int x,int y,int z){
        int ret=maxNum2(x,y);

        int max=maxNum2(ret,z);
        return max;
    }

    public static void main37(String[] args) {
        int num1=30;
        int num2=40;
        int num3=70;
        int ret=maxNum2(num1,num2);
        int maxnum=maxNum3(num1,num2,num3);
        System.out.println(ret);
        System.out.println(maxnum);
    }


    public static void main36(String[] args) {
        int[] array={1,2,3,4,5,6};

        int[]arr={1,2,3,4,4,5,5,5,5,5};
        //        System.out.println(array[5]);
//        int[] array2=new int[]{1,2,3,4,5,6};
//        int[] array3=new int[10];//并没有初始化当前指定的值，默认里面的所有值为0
//        int[] array4={1,2,3};
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+" ");
        }
        System.out.println();
        System.out.println("=============");
        //foreach循环，无法获取到对应的下标   数组中每个元素的类型 : 数组名  遍历数组，取得每一个元素放到x里面
        for (int x:array) {
            System.out.print(x+" ");
        }
        System.out.println();

        //使用Arrays的toString方法，把传入的参数array，表示的数组，以字符串的形式进行输出
        String ret= Arrays.toString(array);
        System.out.println(ret);

        int[] array1={1,2,3,3,4};
        String ret11=Arrays.toString(array1);
        System.out.println(ret11);

    }






    public static int fib2(int n){
        int f1=1;
        int f2=1;
        int f3=0;
        for (int i = 3; i <=n ; i++) {
            f3=f1+f2;
            f1=f2;
            f2=f3;
        }
        return f3;
    }
    public static void main35(String[] args) {
        System.out.println(fib2(6));
    }

    public static int fib(int n){
        if(n==1||n==2){
            return 1;
        }else{
            return fib(n-1)+fib(n-2);
        }
    }
    public static void main34(String[] args) {

        System.out.println(fib(6));
    }

//    sum(1729) = 1729%10 + sum(172) → 9 + sum(172)
//    sum(172)  = 172%10  + sum(17)  → 2 + sum(17)
//    sum(17)   = 17%10   + sum(1)   → 7 + sum(1)
//    sum(1)    = 1（因1<10，触发终止条件）
    public static int sum(int n){
        if(n<10){
            return n;
        }else{
            return n%10+sum(n/10);
        }
    }
    public static void main33(String[] args) {
        int n=1729;
        int ret=sum(n);
        System.out.println(ret);
    }

    public static int add2(int n){
        if(n==1){
            return 1;
        }else{
            return n+add2(n-1);
        }
    }

    public static void main32(String[] args) {
        int n=10;
        int ret=add2(n);

        System.out.println(ret);
    }

    public static int  add1(int x){
        if(x==1){
            return 1;
        }else{
           return x+add1(x-1);
        }
    }
    public static void main31(String[] args) {

        int n=10;
        int ret=add1(n);
        System.out.println(ret);
    }

    public static void print(int n){
        if(n<10){
            System.out.println(n);
        }else{
            print(n/10);
            System.out.println(n%10);
        }
    }
    public static void main30(String[] args) {
        print(1234);
    }

    public static void numEvery(int x){

        if(x>9){
            numEvery(x/10);
        }
        System.out.println(x%10);

    }
    public static void main29(String[] args) {

        int x=1234;
        numEvery(x);
    }


    public static int fac(int x){
        if(x==1){
            return 1;
        }else{
            return x*fac(x-1);
        }
    }

    public static void main28(String[] args) {
        int ret=fac(5);
        System.out.println(ret);
    }

    //方法的重载
    //方法名一样
    //参数列表不一样【个数，类型，顺序】
    //与返回值无关
    public static int add(int x,int y){
        return x+y;
    }

    public static double add(double x,double y){
        return  x+y;
    }

    public  static  int add(int x,int y,short z){
        return x+y+z;
    }

    public static void main27(String[] args) {

        int ret1=add(2,5);
        System.out.println(ret1);
        double ret2=add(2.2,3.6);
        System.out.println(ret2);
//        add(2,5,1);
    }



    public static void main26(String[] args) {

        int a=5;
        int b=5;
//        int c=add(a,b);
//        System.out.println(c);
    }

    public static boolean isLeapyear(int year){

        System.out.println("方法被调用了");

        if ((year%4==0&&year%100!=0)||(year%400==0)){
            return true;
        }else{
            return false;
        }
    }

    public static void main25(String[] args) {

        boolean ret=isLeapyear(2008);
        if(ret==true){
            System.out.println("是闰年");
        }else{
            System.out.println("不是闰年");
        }
    }

    public static void main24(String[] args) {
        int n=7;
        for (int i = 0; i < 32; i++) {
            if(i%2==0){
                System.out.print((n>>i)&1);
            }
        }
        System.out.println();
        for (int i = 0; i < 32; i++) {
            if(i%2!=0){
                System.out.print((n>>i)&1);
            }
        }
    }

    public static void main23(String[] args) {
        for (int i = 0; i < 1000; i++) {
            int temp=i;
            int count=0;
            while(temp!=0){
                count++;
                temp/=10;
            }

            temp=i;
            int  sum=0;
            while(temp!=0){
                sum+=Math.pow(temp%10,count);
                temp/=10;
            }
            if(sum==i){
                System.out.println(i);
            }
        }
    }

    public static void main22(String[] args) {
        int a=18;
        int b=24;
        int c=a%b;
        while(c!=0){
            a=b;
            b=c;
            c=a%b;
        }
        System.out.println(b);
    }

    public static void main21(String[] args) {
        for (int i = 1; i < 10; i++) {
            for (int j = 1; j <= i; j++) {
                System.out.printf("%d*%d=%d\t",j,i,i*j);
            }
            System.out.println();
        }
    }

    public static void main20(String[] args) {
        int count=0;
        for (int i = 2; i < 101; i++) {
            int j = 2;
            for (; j < Math.sqrt(i); j++) {
                if(i%j==0){
                    break;
                }
            }
            if(j>Math.sqrt(i)){
                System.out.println(i);
                count++;
            }
        }
        System.out.println(count);
    }

    public static void main19(String[] args) {
        int num=7;
        int i = 2;
        for (; i < Math.sqrt(num); i++) {
            if(num%i==0){
                break;
            }
        }
        if(i>Math.sqrt(num)){
            System.out.println("是素数");
        }
    }

    public static void main18(String[] args) {
        Scanner scan=new Scanner(System.in);
        while(scan.hasNextInt()){

            int age=scan.nextInt();
            if(age<18){
                System.out.println("少年");
            }else if(age>18&&age<29){
                System.out.println("青年");
            }else if(age>=29&&age<=55){
                System.out.println("中年");
            }else {
                System.out.println("老年");
            }
        }
    }

    public static void main17(String[] args) {

        Random random=new Random();
        int ranNum=random.nextInt(100);
        Scanner scanner=new Scanner(System.in);
        System.out.println("请输入要猜的数字");
        while(true){
            int num=scanner.nextInt();

            if(num<ranNum){
                System.out.println("猜小了");
            }else if (num>ranNum){
                System.out.println("猜大了");
            }else{
                System.out.println("猜对了，答案是"+ranNum);
                break;
            }
        }
    }

    public static void main16(String[] args) {

        Random random=new Random();
        int ranNum=random.nextInt(100);  //[0,100)
        System.out.println(ranNum);
    }

    public static void main15(String[] args) {
        Scanner scan =new Scanner(System.in);

        System.out.println("读入一个整数");
        int a=scan.nextInt();
        System.out.println(a);


        scan.nextLine();
        System.out.println("读入一个字符串");
        String str=scan.nextLine();
        System.out.println(str);


        System.out.println("读入一个小数");

        float f=scan.nextFloat();
        System.out.println(f);
    }

    public static void main14(String[] args) {
        int n=7;
        int count=0;
        while(n!=0){
            n=n&(n-1);
            count++;
        }
        System.out.println(count);
    }
    public static void main13(String[] args) {
        int a=18;
        int b=24;
        int c=a%b;
        while(c!=0){
            a=b;
            b=c;
            c=a%b;
        }
        System.out.println(b);
    }
    public static void main12(String[] args) {
        double sum=0;
        int flag=1;
        for (int i = 1; i < 101; i++) {
            sum=sum+1.0/i*flag;
            flag=-flag;
        }
        System.out.println(sum);
    }
    public static void main11(String[] args) {
        for (int i = 0; i < 999999; i++) {
            int count=0;
            int temp=i;
            while(temp!=0){
                count++;
                temp/=10;
            }
            temp=i;
            int sum=0;
            while(temp!=0){
                sum+=Math.pow(temp%10,count);
                temp/=10;
            }
            if(sum==i){
                System.out.println(i);
            }
        }
    }
    public static void main10(String[] args) {
        //循环输入
        Scanner scanner=new Scanner(System.in);
        while(scanner.hasNextInt()){
            int n=scanner.nextInt();
            System.out.println(n);
        }
    }
    public static void main9(String[] args) {
        int n=7;
        int i = 2;
        for (; i < Math.sqrt(n); i++) {
            if(n%i==0){
                break;
            }
        }
        if(i>Math.sqrt(n)){
            System.out.println(n+"是素数");
        }
    }
    public static void main8(String[] args) {
        int a=10;
        System.out.println();
    }
    public static void main7(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int count=0;
        for (int i = 0; i < 32; i++) {
            if(((n>>i)&1)==1){
                count++;
            }
        }
        System.out.println(count);
    }
    public static void main6(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int s1=scanner.nextInt();
        int s2=scanner.nextInt();
        int min=s1<s2?s1:s2;
        int maxnum=0;
        for (int i = 1; i <= min; i++) {
            if(s1%i==0&&s2%i==0){
                maxnum=i;
            }
        }
        System.out.println(maxnum);
    }
    public static void main5(String[] args) {
        double n=101;
        double sum=0;
        for (double i = 1; i < n; i++) {
            double j=i;
            if(i%2==0){
                j=-i;
            }
            sum+=1.0/j;
        }
        System.out.println(sum);
    }
    public static void main4(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        for (int i = 0; i <= n; i++) {
            if(i<100){
                continue;
            }else{
                int a=i%10;//得到个位数
                int b=i/10%10;//得到十位数
                int c=i/100;//得到百位数
                if(a*a*a+b*b*b+c*c*c==i){
                    System.out.println(i);
                }
            }
        }
    }
    public static void main3(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
        int flag=1;
        for (int i = 2; i < n-1; i++) {
            if(n%i==0){
                flag=0;
                break;
            }
        }
        if(flag==1){
            System.out.println("是素数");
        }else{
            System.out.println("不是素数");
        }
    }
    public static void main2(String[] args) {
        int count=0;
        int n=1;
        for(n=1;n<100;n++) {
            if(n%10==9||n/10==9){
                count++;
            }
        }
        System.out.println(count);
    }
    public static void main1(String[] args) {
        System.out.println("hello world");
    }
}
